public class StockProfit {
    public static void main(String[] args) throws Exception {
        int[] a = {9, 5, 7, 1, 6};

        System.out.println("maxProfit: " + maxProfit(a));
    }
    //股票最大利润: 假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

    /**
     * 动态规划解题思路:
     * dp[i]为前i日的最大利润, prices[i]代表第i天的卖出价格
     * dp[0] = 0;
     * dp[i] = max(dp[i - 1], prices[i] - min(prices[0 : i]))
     * 前i日最大利润 = max(前i - 1日最大利润, 第i日价格 - 前i日最低价格)
     * 每天更新记录最低价格minPrice
     * dp[i] = max(dp[i - 1], prices[i] - minPrice)
     * 由于dp[i] 只与dp[i - 1], minPrice有关,因此可以用一个变量代替dp列表
     * maxProfit = max(maxProfit, prices[i] - minPrice)
     */
    static int maxProfit(int[] arr) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
                                                                                                                                        
        for (int i = 0; i < arr.length; i++) {
           minPrice = Math.min(minPrice, arr[i]);
           maxProfit = Math.max(maxProfit, arr[i] - minPrice);
        }

        return maxProfit;
    }

    static int maxProfit1(int[] arr) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < minPrice) {
                minPrice = arr[i];
            }else if(arr[i] - minPrice > maxProfit) {
                maxProfit = arr[i] - minPrice;
            }
        }

        return maxProfit;
    }

    static int maxProfit2(int[] arr) {
        int maxProfit = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] - arr[i] > maxProfit) {
                    maxProfit = arr[j] - arr[i];
                }
            }
        }

        return maxProfit;
    }
}
